package 数据结构.栈和队列.Algorithm;

import java.util.Deque;
import java.util.LinkedList;

//LeetCode1047 删除字符串中的所有相邻重复项
/*给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

        在 S 上反复执行重复项删除操作，直到无法继续删除。

        在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。*/
public class removeDuplicates {
    public static void main(String[] args) {

    }
    //利用栈去实现即可
    public String removeDuplicates(String s) {
        Deque<Character> deque=new LinkedList<>();
        //
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //如果队列不为空，则去比较
            if(!deque.isEmpty()){
                Character peek = deque.peek();
                if(peek==c){
                    deque.pop();
                }else {
                    deque.push(c);
                }
                //如果队列为空，则去添加
            }else {
                deque.push(c);
            }
        }
        //进行拼接
        StringBuilder builder=new StringBuilder();
        for (Character c : deque) {
            builder.append(c);
        }
        return String.valueOf(builder.reverse());
    }

}
